package org.example.myleet.p424;

public class Solution {

    /**
     * 7 ms
     * 利用窗口长度记录最长的可以完全替换的子序列长度
     */
    public int characterReplacement(String s, int k) {
        int[] charCount = new int[26];
        int l=0, r=0, n = s.length(), max = 0;
        while (r<n) {
            ++charCount[s.charAt(r)-'A'];
            //获得窗口中字母出现次数最多的字母的数目
            max = Math.max(max, charCount[s.charAt(r)-'A']);
            if (r - l + 1 - max > k) {
                //如果窗口长度 - 最多字母数目 = 其他字母数目 > k，则窗口左指针向右移动，相当于窗口大小和上一回合相同
                --charCount[s.charAt(l)-'A'];
                ++l;
            }
            ++r;
        }
        //最终窗口里面的不一定是答案要的字符，但窗口的长度就是答案的最长的子序列的长度
        return r - l;
    }

    /**
     * 23 ms
     * 繁琐版本
     */
//    public int characterReplacement(String s, int k) {
//        int[] charCount = new int[26];
//        int l=0, r=0, max = 0;
//        while (r<s.length()) {
//            ++charCount[s.charAt(r) - 'A'];
//            int[] maxAndOther = findMaxAndOther(charCount);
//            if (maxAndOther[1] > k) {
//                //非最多的字母比k多，所以需要将左边的指针向右移动以使窗口内的非最多字母变成k个
//                do {
//                    --charCount[s.charAt(l) - 'A'];
//                    ++l;
//                    maxAndOther = findMaxAndOther(charCount);
//                } while (maxAndOther[1] > k);
//            } else {
//                //非最多字母小于等于k个时，所有非最多字母可以替换成最多的字母，长度可以为（r - l + 1）
//                max = Math.max(max, r - l + 1);
//            }
//            //右指针向右移动
//            ++r;
//        }
//        return max;
//    }

    /**
     * 找出字母频数中最多的以及其他合共为非最多的
     */
//    private int[] findMaxAndOther(int[] charCount) {
//        int max = 0, maxIdx = 0, otherCount = 0;
//        for (int i=0; i<charCount.length; i++) {
//            if (charCount[i] > max) {
//                max = charCount[i];
//                maxIdx = i;
//                break;
//            }
//        }
//        for (int i=maxIdx+1; i<charCount.length; i++) {
//            if (charCount[i] > max) {
//                otherCount += max;
//                max = charCount[i];
//            } else if (charCount[i] > 0) {
//                otherCount += charCount[i];
//            }
//        }
//        return new int[]{max, otherCount};
//    }
}
